package com.example.leetcode.trainingcamp.week5.Thursday;

/**
 * 给你一个非负整数 x ，计算并返回 x 的 平方根 。
 *
 * <p>由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
 *
 * <p>注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
 *
 * <p>
 *
 * <p>示例 1：
 *
 * <p>输入：x = 4 输出：2 示例 2：
 *
 * <p>输入：x = 8 输出：2 解释：8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/sqrtx 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Test69 {

    public int mySqrt(int x) {
        if (x == 0) return 0;
        int high = (int) Math.sqrt(x);
        int low = 0;
        while (low<= high){
            int mid = low + (high - low) / 2;
            if ((long)mid * mid == x) return mid;
            if ((long) mid * mid <x){
                if ((long) (mid+1) * (mid +1) >x) return mid;
                else if((long) (mid+1) *(mid +1) == x) return mid +1;
                else low = mid + 1;
            }
            if ((long) mid * mid >x){
                if ((long) (mid -1) *(mid -1) >x) high = mid -1;
                else  return mid-1;
            }
        }
        return -1;
    }
}


class Demo69{
  public static void main(String[] args) {
    Test69 t = new Test69();
    int nums = 4;
    System.out.println(t.mySqrt(nums));
  }
}